package com.yww.algorithm.binarytree;

import com.yww.algorithm.binarytree.TreeTraversal;
import com.yww.datastructure.binarytree.TreeNode;
import com.yww.datastructure.stack.LinkedListStack;
import com.yww.datastructure.stack.Stack;

/**
 * @author yww
 * @description 后缀表达式转二叉树
 * @since 2024/2/13 17:50
 */
public class SuffixToTree {
    /**
     * 后缀表达式转换为二叉树
     * 1.遇到数字入栈
     * 2.遇到运算符, 出栈两次, 与当前节点建立父子关系, 当前节点入栈
     */
    public static TreeNode<String> convert(String[] tokens) {
        Stack<TreeNode<String>> stack = new LinkedListStack<>();
        for (String token : tokens) {
            switch (token) {
                case "+":
                case "-":
                case "*":
                case "/":
                    TreeNode<String> right = stack.pop();
                    TreeNode<String> left = stack.pop();
                    stack.push(new TreeNode<>(token, left, right));
                    break;
                default:
                    stack.push(new TreeNode<>(token, null, null));
            }
        }
        return stack.pop();
    }

    public static void main(String[] args) {
        String[] tokens = {"2", "1", "-", "3", "*"};
        TreeNode<String> root = convert(tokens);
        TreeTraversal.postOrder(root, System.out::print);
    }
}
